// #inckude<bits/stdc++.h>
#include "KamaCoder.h"
using namespace std;

const int MAX_INT = 32156;

int KamaCoder94::run() {
  // 输入
  int n, m;
  cin >> n >> m;
  vector<vector<int>> gird;

  int s, t, val;
  for (int i = 0; i < m; i++) {
    cin >> s >> t >> val;
    // 表示s->t, 权值为val
    gird.push_back({s, t, val});
  }

  int start = 1;  // 起点
  int end = n;    // 终点

  // 最小距离矩阵
  vector<int> minDist(n + 1, MAX_INT);
  minDist[start] = 0;

  // 放送n-1次
  for (int i = 0; i < n; i++) {
    // 每次松弛，都是对所有边进行松弛
    for (vector<int> &side : gird) {
      int from = side[0];
      int to = side[1];
      int price = side[2];
      // 松弛操作:
      // minDist[from]!=MAX_INT 防止从未计算过的节点出发
      if (minDist[from] != MAX_INT && minDist[to] > minDist[from] + price) {
        minDist[to] = minDist[from] + price;
      }
    }

    if (minDist[end] == MAX_INT)
      cout << "unconnected" << endl;  // 不能到达终点
    else {
      cout << minDist[end] << endl;
    }
  }
  return 0;
}

int KamaCoder94::run2() {
  // 输入
  int n, m;
  cin >> n >> m;
  vector<list<Edge>> grid(n + 1);  // 邻接表,grid[0]表示from节点

  int p1, p2, val;
  // 将所有边保存起来
  for (int i = 0; i < m; i++) {
    cin >> p1 >> p2 >> val;
    // p1 ->p2 权重 val
    grid[p1].push_back(Edge(p2, val));
  }
  int start = 1;  // 起点
  int end = n;    // 终点

  vector<int> minDist(n + 1, MAX_INT);
  minDist[start] = 0;

  // 定义队列: 只存放从该节点出发
  queue<int> que;
  que.push(start);

  while (!que.empty()) {
    int curnode = que.front();
    que.pop();

    // 遍历从该节点为起始的边
    for (Edge edge : grid[curnode]) {
      int to = edge.to;
      int value = edge.val;
      if (minDist[to] > minDist[curnode] + value) {
        minDist[to] = minDist[curnode] + value;
        que.push(to);
      }
    }
  }
  // 输出结果
  if (minDist[end] == MAX_INT)
    cout << "unconnected" << endl;  // 不能到达终点
  else {
    cout << minDist[end] << endl;
  }
  return 0;
}